package nwsimplex.graph;

import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;

/**
 * A Datastructure that represents a Spanning Tree, which is a tree that
 * contains all vertices of a Graph. Since each SpanningTreeOld is connected to
 * each node adding a new edge requires to remove another edge, to obtain a
 * cyclefree tree structure.
 *
 * Since this SpanningTreeOld is used for the networksimplex algorithm. each edge
 * within the spanningtree satisfies has reduced costs of zero.
 *
 * @author mfj
 */
public class SpanningTree implements Iterable<Vertex> {

    private final Vertex root;
    private final Collection<Edge> artificialEdges;
    private final TreeIterator treeIterator;

    public SpanningTree(Vertex root, Collection<Edge> artificialEdges) {
        this.root = root;
        this.treeIterator = new TreeIterator(root);
        this.artificialEdges = artificialEdges;
        for (Edge edge : artificialEdges) {
            if (edge.from == root) {
                addToTree(edge.to, edge);
            } else if (edge.to == root) {
                addToTree(edge.from, edge);
            } else {
                throw new IllegalArgumentException("invalid initial edges");
            }
        }
    }

    /**
     * Adds a new edge to this spanning tree and removes the edge which is the
     * upward connecting arch of the lowerLeaving vertex.
     *
     * @param entering the entering arch
     * @param leaving the eaving arch
     * @param lowerEntering the lower vertex of the entering arch
     */
    public void addEdge(Edge entering, Edge leaving, Vertex lowerEntering) {
        // removes leaving edge from tree
        Vertex lowerLeaving = leaving.from.depth > leaving.to.depth ? leaving.from : leaving.to;
        removeFromTree(lowerLeaving);

        // reverse predessesor relations from leaving to entering arc
        Vertex next, prev = null, curr = lowerEntering;
        while (curr != null) {
            next = curr.parent;
            curr.parent = prev;
            prev = curr;
            curr = next;
        }


        // add entering arc
        addToTree(lowerEntering, entering);
        updatePotentials(lowerEntering);
    }

    private void removeFromTree(Vertex v) {
        Vertex parent = v.parent;
        v.treeEdge = null;
        v.parent = null;

        Vertex left = v.leftSibbling, right = v.rightSibbling;
        if (left != null) {
            left.rightSibbling = right;
        }
        if (right != null) {
            right.leftSibbling = left;
        }
        v.leftSibbling = v.rightSibbling = null;

        if (v == parent.child) {
            parent.child = v.rightSibbling;
        }
    }

    private void addToTree(Vertex v, Edge e) {
        v.treeEdge = e;
        Vertex parent = e.from == v ? e.to : e.from;
        v.parent = parent;
        if (parent.child == null) {
            parent.child = v;
        } else {
            parent.child.leftSibbling = v;
            v.rightSibbling = parent.child;
            parent.child = v;
        }
    }

    private void updatePotentials(Vertex lowerEntering) {
        treeIterator.setRoot(lowerEntering);
        Vertex v;
        while ((v = treeIterator.next()) != null) {
            Edge e = v.treeEdge;
            v.potential += e.isUpwardPointing()
                    ? e.reducedCost() - v.potential : v.potential - e.reducedCost();

            v.depth = v.parent.depth;
        }
    }

    public Vertex getRoot() {
        return root;
    }

    public Iterator<Edge> artificialEdgeIterator() {
        return Collections.unmodifiableCollection(artificialEdges).iterator();
    }

    public CycleIterator getCycleIterator(Vertex left, Vertex right) {
        return new CycleIterator(left, right);
    }

    @Override
    public Iterator<Vertex> iterator() {
        return new TreeIterator(root);
    }
}
